
package redeS.visualizacao;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collection;
import java.util.Collections;
import peersim.config.Configuration;
import peersim.core.CommonState;
import peersim.core.Linkable;
import peersim.core.Network;

/**
 * Gera um grafo de lista de vizinhos conforme a arquitetura da rede. Essa classe tem
 * propósito de observar a rede mais eficientemente.
 * @author thiago-pc
 */

public class P2PGraph {
	
	private int pid;
	
	/**
	 * Constrói um grafo de lista de vizinhos. Inicialmente é um grafo vazio. Use {@link #updateGraph()}
	 * para gerar o grafo.
	 * @param pid ID do protocolo (um Linkable) obtido com {@link Configuration#getPid(String)}
	 */
	public P2PGraph(int pid){
		this.pid = pid;
	}

	/**
	 * Número de vizinhos do nó de índice i.
	 * @return Tamanho do vetor de vizinhos de i.
	 */
	public int degree(int i) {
		Linkable prot = (Linkable)Network.get(i).getProtocol(pid);
		return prot.degree();
	}

	/**
	 * Retorna os índices dos vizinhos de i na forma de uma coleção (a saber, um ArrayList).
	 * Use esse método se for asolutamente necessário, caso contrário prefira usar
	 * {@link #getNeighboursArray(int)}, é mais rápido e gasta menos memória.
	 */
	public Collection<Integer> getNeighbours(int i) {
		ArrayList<Integer> list = new ArrayList<Integer>();
		Integer[] neighbours = new Integer[degree(i)];
		int[] neigh = getNeighboursArray(i);
		
		for(int j=0; j<neighbours.length; j++){
			neighbours[j] = neigh[j];
		}
		
		Collections.addAll(list, neighbours);
		return list;
	}
	
	/**
	 * Retorna os índices dos vizinhos de i na forma de uma array de inteiros.
	 */
	public int[] getNeighboursArray(int i) {
		Linkable prot = (Linkable)Network.get(i).getProtocol(pid);
		int[] resp = new int[prot.degree()];
		
		for(int j=0; j<resp.length; j++){
			resp[j] = prot.getNeighbor(j).getIndex();
		}
		return resp;
	}

	/**
	 * Retorna o clone() do nó {@link Network#get(int)}.
	 * Se quiser pegar o nó de verdade use o método estático da classe {@link Network} acima.
	 */
	public Object getNode(int i) {
		return Network.get(i).clone();
	}

	/**
	 * Informa se aresta existe.
	 */
	public boolean isEdge(int i, int j) {
		Linkable prot = (Linkable)Network.get(i).getProtocol(pid);
		return prot.contains(Network.get(j));
	}

	/**
	 * Número de nós do grafo.
	 */
	public int size() {
		return Network.size();
	}
	
	//----------------------------------------------------------------------------
	// ALGORIMOS DE GRAFO
	//----------------------------------------------------------------------------
	// esse espaço pode ser preenchido com mais algoritmos caso seja necessário
	
	// Constantes e variáveis para um dfs simles
	private final byte BRANCO = 'B';
	private final byte PRETO = 'P';
	private byte[] cores = new byte[Network.size()];
	
	// Coleções para armazenar conjuntos do grafo
	private ArrayList<int[]> resp;
	private int[] component;
	private int componentIndex;
	
	// dfs simples
	private void dfs(int from){
		cores[from] = PRETO;
		for(int i : getNeighboursArray(from)){
			if(cores[i] == BRANCO){
				dfs(i);
			}
		}
	}
	
	// um método pra saber se tem uma cor no vetor
	private boolean coresContains(byte colors[] ,byte color){
		for(byte i : colors){
			if(i==color){
				return true;
			}
		}
		return false;
	}
	
	/**
	 * Verifica se o grafo atual é totalmente conectado.
	 */
	public boolean isFullyConected(){
		if(cores.length != size()){
			cores = new byte[size()];
		}
		Arrays.fill(cores, BRANCO);
		dfs(0);
		return !coresContains(cores,BRANCO);
	}
	
	/**
	 * Se esse grafo não for totalmente conectado os nós não conectados podem estar conectados
	 * a outros nós formando uma ou mais componentes não-conectadas. Esse método retorna n
	 * componentes não conectadas num ArrayList de vetor de inteiros. Cada ArrayList é uma
	 * das n componentes não-conectadas e o int[] são os nós que formam essa componente.
	 * A escolha dos elementos que farão parte da resposta é totalmente aleatória.
	 * @param n Tamanho do ArrayList
	 * @param lenght Número de nós na componente não conectada
	 * @return Um ArrayList< int[] > como descrito acima. Null se não houver n componentes
	 * não-conectados. Vetores que não atingirem o tamanho lenght serão preenchidos com o
	 * seu primeiro elemento.
	 */
	public ArrayList<int[]> getNotConectedComponts(int n ,int lenght){
		resp = new ArrayList<int[]>();
		byte cores2[] = new byte[size()];
		int from = 0;
		
		int compSerieSize, respSerieSize = 0;	
		int compLastProb, respLastProb = 100;
		
		if(cores.length != size()){
			cores = new byte[size()];
		}
		Arrays.fill(cores2, BRANCO);		
		while(coresContains(cores2, BRANCO)){
			
			component = new int[lenght];
			componentIndex = 0;
			compSerieSize = 0;
			compLastProb = 100;
			Arrays.fill(cores, BRANCO);
			dfs(from);
			for(int i=0; i<cores.length; i++){
				if(cores[i] == PRETO){
					if(componentIndex < lenght){
						component[componentIndex] = i;
						componentIndex++;
						compLastProb = 100;
					}
					else{
						compLastProb = nextProbability(compLastProb, compSerieSize);
						if(Math.abs(CommonState.r.nextInt() % 100) < compLastProb){
							int index = Math.abs(CommonState.r.nextInt() % lenght);
							component[index] = i;
						}
					}
					cores2[i] = PRETO;
					compSerieSize++;
				}
				else if(cores2[i]==BRANCO){
					from = i;
				}
			}
			
			while(componentIndex < lenght){
				component[componentIndex] = component[0];
				componentIndex++;
			}
			
			if(resp.size() < n){
				resp.add(component);
				respLastProb = 100;
			}
			else{
				respLastProb = nextProbability(respLastProb, respSerieSize);
					if(Math.abs(CommonState.r.nextInt() % 100) < respLastProb){
						int index = Math.abs(CommonState.r.nextInt() % n);
						resp.set(index, component);
					}
			}
			respSerieSize++;
		}
		if(resp.size() < n){
			return null;
		}
		return resp;
	}
	
	private int nextProbability(int lastProb, int serieSize){
		if(serieSize==0) return 100;
		return (lastProb*serieSize)/(serieSize+1);
	}
}